//给定一个三角形 triangle ，找出自顶向下的最小路径和。 
//
// 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果
//正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。 
//
// 
//
// 示例 1： 
//
// 
//输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
//输出：11
//解释：如下面简图所示：
//   2
//  3 4
// 6 5 7
//4 1 8 3
//自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
// 
//
// 示例 2： 
//
// 
//输入：triangle = [[-10]]
//输出：-10
// 
//
// 
//
// 提示： 
//
// 
// 1 <= triangle.length <= 200 
// triangle[0].length == 1 
// triangle[i].length == triangle[i - 1].length + 1 
// -10⁴ <= triangle[i][j] <= 10⁴ 
// 
//
// 
//
// 进阶： 
//
// 
// 你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？ 
// 
// Related Topics数组 | 动态规划 
//
// 👍 1114, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.Arrays;
import java.util.List;

class Triangle {
    public static void main(String[] args) {
        Solution solution = new Triangle().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 自顶向下
        // https://leetcode.cn/leetbook/read/path-problems-in-dynamic-programming/r8h07j/
    /*public int minimumTotal(List<List<Integer>> triangle) {
        // 2
        // 3 4
        // 6 5 7
        // 4 1 8 3
        // 滚动数组优化，含义是到达点(i,j)的最短路径为dp[i][j]
        int n = triangle.size();
        int ans = Integer.MAX_VALUE;
        int[][] dp = new int[2][n];

        // 滚动数组不能全部进行初始化，需要在遍历中来进行初始化
//            for (int i = 0; i < 2; i++) {
//                Arrays.fill(dp[i], Integer.MAX_VALUE);
//            }

        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i + 1; j++) {
                int val = triangle.get(i).get(j);
                dp[i][j] = Integer.MAX_VALUE;
                // 第一列不能从左上角推出来，最右边不能从上边推出来
                if (j != 0) dp[i % 2][j] = Math.min(dp[(i - 1) % 2][j - 1] + val, dp[i % 2][j]);
                if (j != i) dp[i % 2][j] = Math.min(dp[(i - 1) % 2][j] + val, dp[i % 2][j]);
            }
        }

        for (int i = 0; i < n; i++) {
            ans = Math.min(ans, dp[(n - 1) % 2][i]);
        }

        return ans;
    }*/

        // 自底向上
        public int minimumTotal(List<List<Integer>> triangle) {
            // 2
            // 3 4
            // 6 5 7
            // 4 1 8 3
            int n = triangle.size();
            int[][] dp = new int[n][n];
            for(int i = 0; i < n; i++) dp[n - 1][i] = triangle.get(n - 1).get(i);
            for (int i = n - 2; i >= 0; i--) {
                for (int j = i; j >= 0; j--) {
                    int val = triangle.get(i).get(j);
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + val;
                }
            }

            return dp[0][0];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
